package com.guaoran.algorithm.binary.search;

/**
 * @Auth gucheng
 * @Desc 使用二分查找法查询有序数组
 *
 * @Date 2020/12/28 下午5:50
 */
public class SearchInRotatedSortedArray {
    public static void main(String[] args) {
        int[] num = {1,2,3,4};
        int target = 1;
        System.out.println(search(num, target));
        System.out.println(search2(new int[]{2,5,6,0,0,1,2},0));
        System.out.println(search2(new int[]{1,1,1,1,1,2,1,1,1,1},2));
    }

    /**
     *  不存在重复的数值 ==》 [4,5,6,7,0,1,2]
     * https://leetcode.com/problems/search-in-rotated-sorted-array/
     * @param num
     * @param target
     * @return
     */
    public static int search(int[] num,int target){
        if(num == null || num.length == 0){
            return -1;
        }

        int start = 0;
        int end = num.length - 1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(num[mid] == target) return mid;
            if(num[mid]>num[start]){
                if(num[mid] >= target && target >= num[start]){
                    end = mid;
                }else {
                    start = mid;
                }
            }else{
                if(num[mid]<=target && target<=num[end]){
                    start = mid;
                }else {
                    end = mid;
                }
            }
        }
        if(num[start]==target) return start;
        if(num[end] ==target) return end;
        return  -1;
    }

    /**
     * 存在重复的值 ==》 [2,5,6,0,0,1,2]
     * https://leetcode.com/problems/search-in-rotated-sorted-array-ii
      * @param nums
     * @param target
     * @return
     */
    public static boolean search2(int []nums,int target){
        if(nums == null || nums.length == 0){
            return false;
        }
        int start = 0;
        int end = nums.length -1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start)/2;
            if(nums[mid] == target) {
                return true;
            }

            if(nums[mid] > nums[start]){
                if(target <= nums[mid] && target >= nums[start]){
                    end = mid;
                }else {
                    start = mid;
                }
            } else if (nums[mid] < nums[start]) {
                if(target >= nums[target] && target <= nums[end]){
                    start = mid;
                }else {
                    end = mid;
                }
            } else {
                start ++ ;
            }

        }

        if(nums[start] == target || nums [end] == target){
            return true;
        }
        return false;
    }
}
